package math;


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 判断分数是否是最简
 * 力扣1447. 最简分数
 * 给你一个整数 n ，请你返回所有 0 到 1 之间（不包括 0 和 1）满足分母小于等于  n 的 最简 分数 。分数可以以 任意 顺序返回。
 * @author HuWLin
 * */
public class Denominator {
    /*
    *
    * 欧几里得算法，最大公约数（Greatest Common Divisor）缩写为GCD。
    * 假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：
    * 1997 / 615 = 3 (余 152)
    * 615 / 152 = 4(余7)
    * 152 / 7 = 21(余5)
    * 7 / 5 = 1 (余2)
    * 5 / 2 = 2 (余1)
    * 2 / 1 = 2 (余0)
    * 至此，最大公约数为1
    * 以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。
    * */
    public int gcd(int a,int b) {
        return a % b == 0 ? b : gcd(b,a % b);
    }

    public List<String> simplifiedFractions(int n) {
        List<String> res = new ArrayList<>();
        for(int i = 2;i <= n;i ++){
            for(int j = 1;j < i;j ++){
                if(gcd(j,i) == 1){
                    res.add(j + "/" + i);
                }
            }
        }
        return res;
    }

}
